﻿#define _CRT_SECURE_NO_WARNINGS
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，
//返回 true ；否则，返回 false 。
//单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是
//那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
//
//示例 1：
//输入：board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]],
//word = "ABCCED"
//输出：true
//示例 2：
//
//输入：board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], 
//word = "SEE"
//输出：true
//示例 3：
//
//输入：board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]],
//word = "ABCB"
//输出：false

//解题思路：
//1.先在二维数组中找与word[0]相同的元素，进入回溯函数
//2.回溯函数内：从该元素开始，找其上下左右等于word[1]的元素，然后再进入回溯函数
//  中从该元素的上下左右找满足word[2]的元素，以此类推，假如找到某个位置时，其上下左右的
//  元素都不满足word的当前位置的元素，就回退当上一层，并进行相应的回溯操作
//3.当wordTop的大小等于word的长度时，已经查找完毕（用bool result 的值来标志该二维数组是否能
//  构成word数组

//写回溯代码的步骤：
//1.确定函数参数
//2.确定终止条件或者满足要求的条件
//3.单层逻辑操作

bool result;
int used[6][6];//用来标志某处的元素已被使用，防止重复使用
int n, m, wordTop, len;
void backtracking(int index_r, int index_c, int row, int col, char** board, char* word)
{
    //满足要求的条件：
    if (board[index_r][index_c] == word[wordTop] && used[index_r][index_c] != 1)
    {
        wordTop++;
        used[index_r][index_c] = 1;//标志该位置的元素已被使用
        if (wordTop == len)//确定终止条件
        {
            result = true;
        }
     else//寻找下一个目标word[wordTop]
    {
     if (index_r - 1 >= 0) { backtracking(index_r - 1, index_c, row, col, board, word); }//当前位置的上方
     if (index_r + 1 <= row - 1) { backtracking(index_r + 1, index_c, row, col, board, word); }//下方
     if (index_c - 1 >= 0) { backtracking(index_r, index_c - 1, row, col, board, word); }//左边
     if (index_c + 1 <= col - 1) { backtracking(index_r, index_c + 1, row, col, board, word); }//右边
            
     wordTop--;//走到这一步时，由于上面四个步骤已经走完，说明没有找到目标元素，则要进行回溯操作，回到上一层
     used[index_r][index_c] = 0;//回到上一层前，当前位置处的元素要被标志成未被使用
        }
    }
}
bool exist(char** board, int boardSize, int* boardColSize, char* word) {
    m = boardSize;  //二维数组有多少行
    n = *boardColSize;  //二维数组有多少列
    wordTop = 0;  //待查找的word数组的元素的当前位置
    len = strlen(word);  //word数组的长度
    result = false;  //将结果默认为false

    if (len > (boardSize * (*boardColSize)))//特殊情况，word数组元素个数大于二维数组的
    {                                       //元素个数
        return result;
    }
    int i, j;
    for (i = 0; i < m; i++)//二维数组的元素都标志为未被使用
    {
        for (j = 0; j < n; j++)
        {
            used[i][j] = 0;
        }
    }
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (board[i][j] == word[0])//找到与第一个元素相同的位置，
            {    //从该位置向周围开始搜索
                backtracking(i, j, m, n, board, word);
                if (result == true)//如果result已经为true,说明已经满足要求，没必要再继续循环
                {
                    return result;
                }
            }
        }
    }
    return false;
}
int main()
{
    char** board = (char**)malloc(sizeof(char*) * 3);
    char word[] = "AAB";
    int i, j; int col = 3;
    for (i = 0; i <=2; i++)
    {
        char* str = (char*)malloc(sizeof(char) * 3);
        board[i] = str;
    }
    board[0][0] = 'C';board[0][1] = 'A';board[0][2] = 'A';
    board[1][0] = 'A';board[1][1] = 'A';board[1][2] = 'A';
    board[2][0] = 'B';board[2][1] = 'C';board[2][2] = 'D';
    bool ret = exist(board, 3, &col, word);
    printf("%d", ret);
}